package com.shm.leetcode;

import java.util.*;

/**
 * 260. 只出现一次的数字 III
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
 * <p>
 * 示例 :
 * <p>
 * 输入: [1,2,1,3,2,5]
 * 输出: [3,5]
 * 注意：
 * <p>
 * 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
 * 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 *
 * @author SHM
 */
public class SingleNumberIII {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        Set<Integer> set = map.keySet();
        List<Integer> list = new ArrayList<>();
        for (Integer i : set) {
            if (map.get(i) == 1) {
                list.add(i);
            }
        }
        int[] arr = new int[2];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public int[] singleNumber_2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int[] arr = new int[2];
        int idx = 0;
        for (Integer integer : set) {
            arr[idx++] = integer;
        }
        return arr;
    }

    /**
     * 思路：
     * 现在数组中有两个数字只出现1次，直接异或一次只能得到这两个数字的异或结果，但光从这个结果肯定无法得到这个两个数字。因此基于single number I 的思路——数组只能有一个数字出现1次。
     * <p>
     * 设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。由于A，B肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。而这个数组中其它数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A，B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位就说明A，B在这一位上是不相同的。
     * <p>
     * 比如
     * <p>
     * <p>
     * int a[] = {1, 1, 3, 5, 2, 2}
     * 整个数组异或的结果为3^5，即 0x0011 ^ 0x0101 = 0x0110
     * <p>
     * 对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是1分成两组。
     * <p>
     * a[0] =1  0x0001  第一组
     * <p>
     * a[1] =1  0x0001  第一组
     * <p>
     * a[2] =3  0x0011  第二组
     * <p>
     * a[3] =5  0x0101  第一组
     * <p>
     * a[4] =2  0x0010  第二组
     * <p>
     * a[5] =2  0x0010  第二组
     * 第一组有{1,1,5}，第二组有{3,2,2}，然后对这二组分别执行“异或”解法就可以得到5和3了。
     * <p>
     * 代码：
     * 时间复杂度O(n)，空间复杂度O(1)
     * <p>
     * 作者：BugFreezrr
     * 链接：https://leetcode-cn.com/problems/single-number-iii/solution/java-yi-huo-100-yao-shi-kan-bu-dong-wo-jiu-qu-chu-/
     *
     * @param nums
     * @return
     */
    public int[] singleNumber_3(int[] nums) {
        int[] res = new int[2];
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        int temp = 1;
        while (true) {
            if ((xor & 1) == 1) {
                break;
            }
            temp <<= 1;
            xor >>= 1;
        }

        for (int num : nums) {
            if ((num & temp) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}
